package DataStructureAndAlgorithm.GraphTheory.应用;
import java.util.*;
//链接：https://leetcode-cn.com/problems/network-delay-time/
public class Dijkstra_leetcode_743 {
    int node;
    boolean[] st;
    public int networkDelayTime(int[][] times, int n, int k) {
        node = times.length;
        int[][] grid = new int[n + 1][n + 1];
        int[] dist = new int[n+1];
        st = new boolean[n+1];
        int res = 0;
        for (int i = 0; i <= n; i ++){
            Arrays.fill(grid[i],200000);
        }
        for (int i = 0; i < node; i++){
            grid[times[i][0]][times[i][1]] = times[i][2];
        }
        //Dijkstra可以求出从起点到任意一个点的最短距离
        //因此，只要跑一遍dijkstra，再对所有最小路径求一个max。就能保证取到到达所有点的最短距离
        Dijkstra(dist,grid,n,k);
        for (int i = 1; i <= n; i++){
            if (dist[i] == 200000)return -1;
            res = Math.max(res,dist[i]);
        }
        return res;
    }
    void Dijkstra(int[] dist,int[][] grid,int n,int k){
        Arrays.fill(dist,200000);
        dist[k] = 0;
        for (int i = 0; i < n; i++){
            //用t来求i点到下一个点的min
            int t = -1;
            //从i点出发，遍历一遍整个图，更新一遍t
            for (int j = 1; j <= n; j++){
                //如果点没被访问过，或者距离可以更小，则更新t
                if (!st[j] && (t == -1 || dist[t] > dist[j])){
                    t = j;
                }
            }
            st[t] = true;
            //用t点，来更新其后面的所有点到k点的距离
            for (int j = 1; j <= n; j++){
                dist[j] = Math.min(dist[j],dist[t] + grid[t][j]);
            }
        }
    }
}
/*
743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
 */